package com.acwing.partition4;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/1/19 11:08
 */
public class AC346走廊泼水节 {

    private static final int N = 6010;
    private static int[][] edges = new int[N][3];
    private static int[] parent = new int[N], size = new int[N];

    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(reader.readLine());
        while (t-- > 0) {
            n = Integer.parseInt(reader.readLine());
            reset();
            for (int i = 0; i < n - 1; i++) {
                String[] s = reader.readLine().split("\\s+");
                int u = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]), w = Integer.parseInt(s[2]);
                edges[i] = new int[]{u, v, w};
            }
            writer.write(kruskal() + "\n");
        }
        writer.flush();
    }

    private static void reset() {
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    private static int kruskal() {
        int answer = 0;
        Arrays.sort(edges, 0, n - 1, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        for (int i = 0; i < n - 1; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            int a = find(u), b = find(v);
            if (a != b) {
                //两个连通块合并成一个完全无向图需要连接size[a] * size[b] - 1条边
                answer += (size[a] * size[b] - 1) * (w + 1);
                parent[a] = b;
                size[b] += size[a];
            }
        }
        return answer;
    }

    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
}
